A binary tree structure (sometimes referred to simply as a binary tree) is a non-linear data structure in which each node has at most two child nodes. A parent node is a node with at least one child. A leaf node is a node without any children. A full binary tree is a tree in which every node has two children, except the leaf nodes.
Binary trees have many applications. For example, binary trees may be used in language parsing, such as by applying a binary expression tree. Some compilers use a binary expression tree to represent an arithmetic expression, for example, with the nodes of the binary expression tree being binary operators and operands. Binary trees are also used in cryptography. For example, a Merkle tree, as known as a hash tree, is a complete binary tree. A complete binary tree is a binary tree in which every level, except possibly the last level, is completely filled. Currently, Merkle trees are used in peer-to-peer networks to check that data blocks received from other peers in the network are received undamaged and unaltered.
Binary trees are also used in broadcast encryption. The area of broadcast encryption was first formally studied by Fiat and Naor in 1994. In 2001, Naor et al. published a paper entitled “Revocation and Tracing Schemes for Stateless Receivers.” The paper discussed broadcast encryption in a stateless receiver scenario. A stateless receiver is a receiver that is not capable of recording, or cannot be relied upon to record, a past history of transmissions and change its state accordingly. This scenario is particularly applicable to receivers that are not constantly on-line, such as media players, e.g., a CD or DVD player where the “transmission” is the current disc. In the paper, Naor et al. described a broadcast encryption scheme using binary trees and a subset difference method.